package leetcode.l0606;

import java.util.Arrays;
import java.util.Collections;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须 原地 修改，只允许使用额外常数空间。
 * @author Retain
 * @date 2021/6/6 15:54
 */
public class Medium_下一个排列_31 {


    /**
     * 首先想法是倒序遍历数组，交换第一个遇到的符合条件的数字对.
     * 部分正确，但是题意理解错了。部分结果不正确
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int modCound = 0;
        for (int i = len - 1; i > 0 ; i--) {
            if (nums[i] > nums[i - 1]) {
                int temp = nums[i];
                nums[i] = nums[i-1];
                nums[i-1] = temp;
                modCound++;
                break;
            }
        }
        if (modCound == 0) {
            reverse(nums,0, len);
        }
    }

    public void reverse(int[] nums,int start, int end) {
        for (int i = start; i < end / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[nums.length - i - 1];
            nums[nums.length -i - 1] = temp;
        }
    }


    /**
     * 官方题解：逆序查找第一个非降序的元素，再逆序查找比该元素大的最小的元素，交换两个元素，将前面指针后面的元素反转
     * @param nums
     */
    public void nextPermutation2(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = 0;
        for (int i = len - 1; i > 0 ; i--) {
            if (nums[i] < nums[i - 1]) {
                left = i - 1;
                break;
            }
        }
        for (int i = len - 1; i > 0 ; i--) {
            if (nums[i] > nums[left]) {
                right = i;
                break;
            }
        }
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;

        reverse(nums,left + 1,len);
    }

    /**
     * 官方题解
     * @param nums
     */
    public void nextPermutation3(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}
